/*
https://leetcode-cn.com/problems/beautiful-array/solution/piao-liang-shu-zu-by-leetcode/
 */
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution932 {

    Map<Integer,int[]> map=new HashMap<>();

    public int[] beautifulArray(int n) {
        if (map.containsKey(n)){
            return map.get(n);
        }
        int[] ans=new int[n];
        if (n==1){
            ans[0]=1;
        }else{
            int cur=0;
            int[] g=beautifulArray((n+1)/2);
            for (int i : g) {
                ans[cur]=2*i-1;
                cur++;
            }
            g=beautifulArray(n/2);
            for (int i : g) {
                ans[cur]=2*i;
                cur++;
            }
        }
        map.put(n,ans);
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution932().beautifulArray(4)));
    }
}
